package heap;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 *  题目 ：和最小的k个数对
 *  题目详述 ：
 *  给定两个以升序排列的整数数组 nums1 和 nums2,以及一个整数 k。
 *
 * 定义一对值(u,v)，其中第一个元素来自nums1，第二个元素来自 nums2。
 *
 * 请找到和最小的 k个数对(u1,v1), (u2,v2) ... (uk,vk)。
 */
public class KSmallestPairs {
    /**
     *  核心思想 ：
     *  （1）利用最大堆来存储所有数对中k个最小值，同时保证了最大堆的栈顶元素为所存储的最小数对中的最大值；
     *  即，后续新插入的数对只要满足小于最大堆的栈顶元素，就可以插入堆中；
     *  （2）同时，可以利用所组成数对的两个整数数组是以升序拍的整数数组，所以可以充分地去利用此特性；
     *  即，只需要对于两个整数数组的前k个元素进行排序比较即可；
     */
//    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
//        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
//                // 设定堆的比较规则，从而使得此堆为最大堆；
//                // 实现方式 ：即，通过实现Comparable接口，来自定义比较规则；
//                (p1 , p2) -> (p2[0] + p2[1]) - (p1[0] + p1[1])
//        );
//        // 根据所传入的两个整数数组为升序排列的；
//        // 所以，可知遍历获取两个升序数组的前k个数组元素即可
//        for(int i = 0;i < Math.min(nums1.length , k);i++){
//            for(int j = 0;j < Math.min(nums2.length , k);j++){
//                if(maxHeap.size() < k){
//                    maxHeap.offer(new int[]{nums1[i] , nums2[j]});
//                }
//                else{
//                    int[] peek = maxHeap.peek();
//                    if(nums1[i] + nums2[j] < peek[0] + peek[1]){
//                        maxHeap.poll();
//                        maxHeap.offer(new int[]{nums1[i] , nums2[j]});
//                    }
//                }
//            }
//        }
//        // 将int[]整数数组，转化为List集合类型，使得返回值类型相符合
//        List<List<Integer>> result = new ArrayList<>();
//        while(!maxHeap.isEmpty()){
//            int[] ints = maxHeap.poll();
//            result.add(Arrays.asList(ints[0] , ints[1]));
//        }
//        return result;
//    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：由于遍历两个整数数组中的所有元素所需要的时间复杂度：O（k*k）；同时，堆中的插入，修改和删除操作所需要消耗的时间复杂度：O（logk）；
     *  即，最后总的时间复杂度 ：O（k*k*logk）；
     * （2）空间复杂度 ：使用了占用空间为O（k）的最大堆空间；
     */

    /**
     * 核心思想 ；
     * （1）即，充分利用了所传入数组的有序性；
     * 即，构建一个最小堆用来存储当前情况下的最小元素（最小堆的堆顶元素，即为最小元素）；
     * 同时，遍历两个数组，直至凑齐k个最小的数对即可（顺序遍历两个数组即可，由于两个数组中的所有元素都是升序排列的）
     * （2）首先，固定住两个数组中的某个数组的首个元素，遍历另一个数组（直至遍历完另一个数组/直至最小堆到达最大容量）；
     * （3）其次，上述步骤结束后，将当前最小堆中的堆顶元素进行弹出，获取到目前的最小数对；
     * （4）根据，所弹出的最小数对的首个数组元素int[0]，对于int[1]进行 加一操作；
     * 问题 ：为什么不能够对于int[0]进行加一操作？
     * 原因 ：若是对于int[0]进行加一操作的话，即在最小堆中必然存在比起小的数对；
     * （这种情况是不被允许的，因为若是加入一个必然不是当前最小数对的，那么可能意味着还存在着比起更小的数对）
     * (5)循环遍历，直至获取到k个数对（即，已经获取到所有数对中的k个最小数对）
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
                // 定义堆的比较规则，即定义堆为最小堆
                (p1 , p2) -> (nums1[p1[0]] + nums2[p1[1]]) -(nums1[p2[0]] + nums2[p2[1]])
        );

        if(nums2.length > 0){
            for(int i = 0 ;i < Math.min(k , nums1.length);i++){
                // 固定住两个数组中的某个数组的首个元素，遍历另一个数组（直至遍历完另一个数组/直至最小堆到达最大容量）
                minHeap.offer(new int[]{i , 0});
            }
        }
        // 即，使用sum变量来保存所要获取的最小数对数量
        int sum = k;
        List<List<Integer>> result = new ArrayList<>();
        while(sum > 0 && !minHeap.isEmpty()){
            int[] poll = minHeap.poll();
            // 将最小堆中所弹出的最小数对，加入到结果集合中去
            sum--;
            // 每次获取到一个最小数对，就会将所要获取到最小数对总数 进行减一操作
            result.add(Arrays.asList(nums1[poll[0]] , nums2[poll[1]]));
            if (poll[1] < nums2.length - 1){
                minHeap.offer(new int[]{poll[0] , poll[1] + 1});
            }

        }
        return result;
    }
    /**
     * 分析 ：
     * （1）时间复杂度 ：
     *  使用for循环，去给最小堆中添加元素，由于最小堆的最大容量为k，所以 时间复杂度：O（k）；
     *  同时，在遍历最小堆中的元素，进行最小数对的获取时，时间复杂度： O（k）；
     *  同时，对于最小堆中的增加，删除或者修改堆元素的话，所需要的时间复杂度： O（logk）；
     *  ===》 总的来说，总时间复杂度：O（klogk）；
     *  （2）空间复杂度 ：由于需要一个堆大小为k的最小堆，所以空间复杂度 ：O（k）；
     */
}
